package com.explorati.interview.interview.chapterfifteen.sort;

public class MergeSort {

	public void sort(int[] arr) {

		__mergeSort((int[]) arr, 0, arr.length - 1);
	}

	// 递归使用归并排序，对arr[l...r]的范围进行排序
	private void __mergeSort(int[] arr, int l, int r) {

		if (l >= r)
			return;

		int mid = (r + l) / 2;
		__mergeSort(arr, 0, mid);
		__mergeSort(arr, mid + 1, r);
		__merge(arr, l, mid, r);
	}

	// 将arr[l...mid]和arr[mid + 1...r]两部分进行归并
	private void __merge(int[] arr, int l, int mid, int r) {

		int[] aux = new int[r - l + 1];
		for (int i = l; i <= r; i++) {
			aux[i - l] = arr[i];
		}

		int i = l, j = mid + 1;
		for (int k = l; k <= r; k++) {
			if (i > mid) {
				arr[k] = aux[j - l];
				j++;
			} else if (j > r) {
				arr[k] = aux[i - l];
				i++;
			} else if (aux[i - l] < aux[j - l]) {
				arr[k] = aux[i - l];
				i++;
			} else {
				arr[k] = aux[j - l];
				j++;
			}
		}
	}

}
